题解 P3621@洛谷 【[APIO2007]风铃】

CSP2020 快到了，感觉自己 dp 太菜了，补了很多 dp >_<

题意（经过 OI 化魔改）：给定一棵二叉树，每次可以交换一个节点的左右儿子，使这棵二叉树是完全二叉树。

思路：容易想到如下几种情况。

情况 $1$ ：容易想到，若所有叶子节点中最深的深度和最浅的深度之差大于 $1$，那么无解，因为此时没有办法通过交换左右儿子将深度差减少。

情况 $2$ ：如果所有叶子深度均相同，直接输出 $0$。

以上情况可以通过一遍 dfs 求深度解决。

情况 $3$ ：对于一个节点，如果左子树全部为深度浅的节点，且右子树存在深度深的节点，此时需要进行一次交换。

情况 $4$ ：对于一个节点，如果左子树存在深度深、浅的两种节点，且右子树全部为深度深的节点，此时需要进行一次交换。

情况 $5$ ：对于一个节点，如果左、右子树均存在深度深、浅的两种情况，那么无解，因为无论怎么交换，总存在左子树的深度浅的节点比右子树的深度深的节点不符合题意。

以上情况在第二遍 dfs 时统计。

实现细节：第一遍 dfs 就是正常的求深度，没什么好说的，主要说说第二遍 dfs。

第二遍 dfs 的返回值设计为 $0/1/2$，分别表示当前结点为根的子树全部为深度浅的节点、深度深的节点，或者二者皆有。在递归返回的时候，我们判断左、右子树返回值进行处理即可。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, inf = 0x3f3f3f3f; 

int n, son[N][2], mi = inf, ma, ans;
void dfs(int u, int k) {
	if(u == -1) return (mi=min(mi, k)), (ma=max(ma, k)), void();
	dfs(son[u][0], k+1);
	dfs(son[u][1], k+1);
}
int dfs2(int u, int k) {
	if(u == -1) return (k != mi);
	int x = dfs2(son[u][0], k+1);
	int y = dfs2(son[u][1], k+1);
	ans += ((!x && y) || (x == 2 && y == 1));
	if(x == 2 && y == 2) exit((puts("-1"), 0));
	if(x == 2 || y == 2 || x + y == 1) return 2;
	if(!(x + y)) return 0;
	return 1;
}

int main() {
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d%d", &son[i][0], &son[i][1]);
	dfs(1, 0);
	if(ma - mi > 1) return puts("-1"), 0;
	if(ma == mi) return puts("0"), 0;
	int _ = dfs2(1, 0);
	printf("%d\n", ans);
	return 0;
}